Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Граматики передування

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2008
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-31

Частина тексту файла

Міністерство освіти і науки України Національний університет “Львівська політехніка” кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретна математика на тему: „Граматики передування” Зміст 1. Вступ 2. Основні поняття граматики 3. Граматики передування (загальна характеристика) 4. Алгоритм типу «перенос-згортка» 5. Граматики простого передування 6. Граматики розширеного передування 7. Граматики слабкого передування 8. Список використаної літератури Вступ Для створення нових мов програмування необхідно описати правила згідно яких записуються слова мови. Також виникає проблема розпізнавання вхідних слів, а саме чи належать вони даній мові чи ні. Існує декілька методів перевірки належності стрічки до мови, одним з них є алгоритм типу «перенос – згортка». Суть алгоритму полягає у використанні вхідної стрічки, читаючи її з ліва на право, і магазину. На основі того, що знаходиться в магазині і залишилось не опрацьованим на вході, функція f вирішує, перенести даний вхідний символ в магазин чи викликати процедуру згортки. Якщо виконується останнє рішення, то функція g вирішує, яку згортку зробити. Основні поняття граматики Граматика - це математична система, що визначає мову. Одночасно вона є пристроєм , що надає ланцюжкам мови корисну структуру. У граматиці, що визначає мову L, використовуються дві кінцеві непересічні множини символів - множина нетермінальних символів (позначимо N) і множина термінальних символів (позначимо T). З термінальних символів утворюються слова (ланцюжки) обумовленої мови. Основу граматики становить скінченна множина P правил виводу, які описують процес породження ланцюжків мови. Наприклад, правилом може бути пара (AB, CDE). Якщо вже встановлено, що деякий ланцюжок α породжується граматикою (або «виводиться » у ній) і α містить AB, тобто ліву частину цього правила, у якості свого підланцюжка, то можна утворити новий ланцюжок β, замінивши одне входження AB в α на CDE. Тоді говорять, що β виводиться у даній граматиці . Наприклад, якщо ланцюжок FGABH виведений, то FGCDEH теж виведений. Мова, обумовлена граматикою, - це множина ланцюжків, які складаються тільки з терміналів і виводяться, починаючи з одного особливого ланцюжка, що складається з одного виділеного символу, звичайно позначуваного S. Означення. Граматикою називається четвірка G=(N, T, P, S) , де N - скінченна множина нетермінальних символів, або нетерміналів; T - скінченна множина термінальних символів, або терміналів, яка не перетинається з N; P - скінченна підмножина множин ()*N()*(()*. S- виділений символ з N називаний початковим (або вихідним) символом. Контекстно-вільною (надалі будем позначати КВ) називається граматика, якщо кожне правило з Р має вигляд А→α, де АN ,α()*; Граматики передування (загальна характеристика) Найпростіший клас алгоритмів типу "перенос - згортка " базується на так званих відношеннях передування. Для граматики передування межі основи праволінійного ланцюжка можна визначити за допомогою деяких відношень між символами, які входять в даний ланцюжок Техніка розбору, орієнтована на відношеннях передування, використовувалась при побудові аналізаторів для мов програмування однієї з перших. З того часу в літературі появилося декілька видів граматик передування. Ми розглянемо оснований на відношеннях передування детермінований аналіз зліва на право, який проводить правий розбір. При цьому будуть введені граматики передування наступних типів: Простого передування, Розширеного передування, Слабкого передування, Змішаної стратегії передування, Операторного передування. Ключ для розуміння методу розбору по відношенням передування дає визначення відношення  (≥)  між    символами граматики, які при перегляді зліва на право праволінійного ланцюжка ...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини